package com.gxc.sort;

import com.gxc.randomArray.generateRandomArray;

/**
 * 归并排序
 */
public class Merge {

    public static void main(String[] args) {
        int[] arr = generateRandomArray.generateArray(20, 30);
        generateRandomArray.sout(arr);

        //归并排序
        mergeSuanfa(arr, 0, arr.length-1);

        System.out.println("=======排序后=====");

        generateRandomArray.sout(arr);
    }

    private static void mergeSuanfa(int[] arr, int l, int r) {
        if (l == r) return;

        int mid = l + (r-l)/2;
        mergeSuanfa(arr, l, mid);
        mergeSuanfa(arr, mid +1, r);
        merge(arr, l, mid, r);
    }

    private static void merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r-l+1];
        int helpLoc = 0;
        int p1 = l, p2=mid+1;
        while (p1<=mid && p2<=r) {
            help[helpLoc++] = arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
        }
        while (p1<=mid) {
            help[helpLoc++] = arr[p1++];
        }
        while (p2<=r) {
            help[helpLoc++] = arr[p2++];
        }
        for (int i = 0; i < help.length; i++) {
            arr[l+i] = help[i];
        }
    }
}
